///\todo upgrade

//////////////////////////////////////////////////////////////////////////////////
//                                                                              //
//  This file is part of the buola project (https://code.google.com/p/buola/).  //
//                                                                              //
//  Copyright(c) 2007-2012 Xavi Gratal                                          //
//  gratal@gmail.com                                                     //
//                                                                              //
//  Buola is free software: you can redistribute it and/or modify               //
//  it under the terms of the GNU General Public License as published by        //
//  the Free Software Foundation, either version 3 of the License, or           //
//  (at your option) any later version.                                         //
//                                                                              //
//  Buola is distributed in the hope that it will be useful,                    //
//  but WITHOUT ANY WARRANTY; without even the implied warranty of              //
//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the               //
//  GNU General Public License for more details.                                //
//                                                                              //
//  You should have received a copy of the GNU General Public License           //
//  along with buola.  If not, see <http://www.gnu.org/licenses/>.              //
//                                                                              //
//////////////////////////////////////////////////////////////////////////////////

#ifndef _BUOLA_CONTAINER_C2DTREE_H_
#define _BUOLA_CONTAINER_C2DTREE_H_

#include <buola/container/cintrusivelist.h>
#include <buola/utility/random.h>
#include <buola/utility/crect.h>

namespace buola {

///\addtogroup geometry
///@{

////////////////////////////////////////////////////////////////////////////

/// 2D point with integer coordinates

/// represents a point in 2 dimensions, with integer coordinates
///
/// \todo use template parameter for allocator and implement CPoolAllocator
///////////////////////////////////////////////////////////////////////////

template<typename tData>
class C2DTree
{
    enum ENodeState
    {
        NODE_AVAILABLE,
        NODE_DIVIDED,
        NODE_OCCUPIED,
        NODE_TEMPPINNED
    };

    struct SNode;
    typedef CIntrusiveList<SNode> tList;

    ///\todo move this to its own top-level class
    struct SDataHolder
    {
        //by making it a union, we can construct it and destroy it explicitly when needed
        union SUnion
        {
            SUnion() {}
            ~SUnion() {}

            tData mReal;
        } mData;
    };
    
    struct SNode : public tList::SHook,public SDataHolder
    {
        SNode(SNode *pParent,const CRect_i &pR)
            :   mParent(pParent)
            ,   mState(NODE_AVAILABLE)
            ,   mRect(pR)
        {
            mChildren[0]=nullptr;
        }

        SNode *mChildren[4];
        SNode *mParent;
        ENodeState mState;
        CRect_i mRect;
    };

public:
    C2DTree(const CSize_i &pSize,const CSize_i &pMinSize=CSize_i(1,1))
        :   mRoot(nullptr,CRect_i(0,0,pSize.x,pSize.y))
        ,   mMinSize(pMinSize)
    {
        mAvailable.push_back(mRoot);
    }

    ~C2DTree()
    {
        DestroyNode(&mRoot);
    }
    
private:
    void DestroyData(SNode *pNode)
    {
        pNode->mData.mReal.~tData();
    }
    
    SNode *CreateNode(SNode *pParent,const CRect_i &pR)
    {
        SNode *lNode=new SNode(pParent,pR);
        mAvailable.push_back(*lNode);
        return lNode;
    }

    ///destroys the node

    ///If the node is a divided node, it recursively destroys and deletes all children.
    ///
    ///It doesn't delete the node itself
    void DestroyNode(SNode *pNode)
    {
        tList::erase(*pNode);
        
        if(pNode->mState==NODE_OCCUPIED)
            DestroyData(pNode);
        else
        {
            for(int i=0;i<4&&pNode->mChildren[i];i++)
            {
                DestroyNode(pNode->mChildren[i]);
                delete pNode->mChildren[i];
            }
        }
    }
    
    void CollapseNode(SNode *pNode)
    {
        while(pNode)
        {
            for(int i=0;i<4&&pNode->mChildren[i];i++)
            {
                if(pNode->mChildren[i]->mState!=NODE_AVAILABLE)
                    return;
            }

            for(int i=0;i<4&&pNode->mChildren[i];i++)
            {
                DestroyNode(pNode->mChildren[i]);
                delete pNode->mChildren[i];
            }

            pNode->mChildren[0]=nullptr;
            pNode->mState=NODE_AVAILABLE;

            mAvailable.MoveFront(*pNode);
            pNode=pNode->mParent;
        }
    }

    SNode *InsertNode(SNode *pParent,const CSize_i &pSize)
    {
        const CRect_i &lRect=pParent->mRect;

        SNode *lReturn=pParent;
        
        //if there will be space for more nodes, divide it and return one of the children
        if(lRect.w()-pSize.x>=mMinSize.x||lRect.h()-pSize.y>=mMinSize.y)
        {
            int w=lRect.w()-pSize.x;
            int h=lRect.h()-pSize.y;

            int i=0;
            pParent->mChildren[i++]=CreateNode(pParent,CRect_i(lRect.TopLeft(),pSize));

            if (w>=mMinSize.x)
               pParent->mChildren[i++]=CreateNode(pParent,CRect_i(lRect.l+pSize.x,lRect.t,lRect.r,lRect.t+pSize.y));
                
            if(h>=mMinSize.y)
            {
                pParent->mChildren[i++]=CreateNode(pParent,CRect_i(lRect.l,lRect.t+pSize.y,lRect.l+pSize.x,lRect.b));

                if(w>=mMinSize.x)
                    pParent->mChildren[i++]=CreateNode(pParent,CRect_i(lRect.l+pSize.x,lRect.t+pSize.y,
                                                                        lRect.r,lRect.b));
            }

            if(i<4)
                pParent->mChildren[i]=nullptr;

            pParent->mState=NODE_DIVIDED;
            mEvictable.MoveFront(*pParent);

            lReturn=pParent->mChildren[0];
        }

        lReturn->mState=NODE_OCCUPIED;
        mEvictable.MoveFront(*lReturn);

        return lReturn;
    }

    void RemoveNode(SNode *pNode)
    {
        DestroyData(pNode);

        pNode->mState=NODE_AVAILABLE;
        mAvailable.MoveFront(*pNode);

        CollapseNode(pNode->mParent);
    }
    
    static SNode *DataToNode(tData &pData)
    {
        SDataHolder *lHolder=reinterpret_cast<SDataHolder*>(&pData);
        return static_cast<SNode*>(lHolder);
    }
    
public:
    template<typename... tArgs>
    tData *emplace(const CSize_i &pSize,tArgs&&... pArgs)
    {
        for(SNode &lNode : mAvailable)
        {
            if(lNode.mRect.w()>=pSize.x&&lNode.mRect.h()>=pSize.y)
            {
                SNode *lNew=InsertNode(&lNode,pSize);
                return new(&lNew->mData.mReal) tData(std::forward<tArgs>(pArgs)...);
            }
        }

        return nullptr;
    }    

    template<typename... tArgs>
    tData *emplace_force(const CSize_i &pSize,tArgs&&... pArgs)
    {
        for(SNode &lNode : mAvailable)
        {
            if(lNode.mRect.w()>=pSize.x&&lNode.mRect.h()>=pSize.y)
            {
                SNode *lNew=InsertNode(&lNode,pSize);
                return new(&lNew->mData.mReal) tData(std::forward<tArgs>(pArgs)...);
            }
        }

        if(SNode *lEvicted=EvictRandom(pSize))
        {
            SNode *lNew=InsertNode(lEvicted,pSize);
            return new(&lNew->mData.mReal) tData(std::forward<tArgs>(pArgs)...);
        }
        
        return nullptr;
    }

    void clear()
    {
        DestroyNode(&mRoot);

        mRoot.mState=NODE_AVAILABLE;

        mAvailable.push_back(mRoot);
    }

    static CRect_i GetRect(tData &pData)
    {
        return DataToNode(pData)->mRect;
    }
    
    void Pin(tData &pData)
    {
        mPinned.MoveFront(*DataToNode(pData));
    }

    void Unpin()
    {
        mEvictable.MoveFront(mPinned);
    }

    SNode *EvictRandom(const CSize_i &pSize)
    {
        tList lTmpPinned;

        for(SNode &lPinned : mPinned)
        {
            SNode *lNode=lPinned.mParent;
            while(lNode&&lNode->mState!=NODE_TEMPPINNED)
            {
                lNode->mState=NODE_TEMPPINNED;
                lTmpPinned.MoveFront(*lNode);
                lNode=lNode->mParent;
            }
        }

        int lCount=0;
        for(SNode &lEvictable : mEvictable)
        {
            if(lEvictable.mRect.w()>=pSize.x&&lEvictable.mRect.h()>=pSize.y)
                lCount++;
        }

        SNode *lReturn=nullptr;
        
        msg_info() << "lCount=" << lCount << "\n";
        if(lCount)
        {
            lCount=random::get<int>(0,lCount-1);

            for(SNode &lEvictable : mEvictable)
            {
                if(lEvictable.mRect.w()>=pSize.x&&lEvictable.mRect.h()>=pSize.y&&lCount--==0)
                {
                    DestroyNode(&lEvictable);
                    
                    lEvictable.mState=NODE_AVAILABLE;
                    mAvailable.push_front(lEvictable);

                    lReturn=&lEvictable;
                    break;
                }
            }
        }

        while(!lTmpPinned.empty())
        {
            SNode *lNode=&lTmpPinned.front();
            lNode->mState=NODE_DIVIDED;
            mEvictable.MoveFront(*lNode);
        }

        return lReturn;
    }
    
private:
    SNode mRoot;
    CSize_i mMinSize;
    tList mPinned;
    tList mAvailable;
    tList mEvictable;
};

///@}

/*namespace buola*/ }

#endif
